#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <iostream>
typedef char TreeTypeData;
typedef struct TreeNode {
	TreeTypeData val;
	TreeNode* left;
	TreeNode* right;
}Node;
Node* CreatTree(char* node, int* p) {
	if (node[*p] == '#') 
		{ 
			(*p)++; 
			return NULL;
		}
	Node* tmp = (Node*)malloc(sizeof(Node));
	if (tmp == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	tmp->val = node[(*p)++];
	tmp->left = CreatTree(node, p);
	tmp->right = CreatTree(node, p);
	return tmp;
}
void DestoryTree(Node* node) {
	if (node == NULL)
	{
		return;
	}
	DestoryTree(node->left);
	DestoryTree(node->right);
	free(node);
}
void Prevorder(Node* node) {
	if (node == NULL)
		return;
	std::cout << node->val << " ";
	Prevorder(node->left);
	Prevorder(node->right);
}
int BinaryTreeSize(Node* root) {
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int BinaryTreeLeafSize(Node* root) {
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int BinaryTreeLevelKSize(Node* root, int k) {
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
Node* BinaryTreeFind(Node* root, TreeTypeData x) {
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	Node* left = BinaryTreeFind(root->left, x);
	if (left)
		return left;
	Node* right = BinaryTreeFind(root->right, x);
		return right;
}
int main()
{
	char a[] = "abd##e#h##cf##g##";
	int p = 0;
	Node* root = CreatTree(a, &p);
	Prevorder(root);
	int n = BinaryTreeSize(root);
	std::cout << n << std::endl;
	std::cout << BinaryTreeLeafSize(root) << std::endl;
	std::cout << BinaryTreeLevelKSize(root, 3) << std::endl;
}